#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int minDistance(char* word1, char* word2) {
    int dp[501][501];
    memset(dp, 0, 501 * 501 * sizeof(int));
    int i = 0, j = 0;
    while (word1[i] != '\0') {
        dp[i][0] = i;
        i++;
    }
    dp[i][0] = i;
    while (word2[j] != '\0') {
        dp[0][j] = j;
        j++;
    }
    dp[0][j] = j;
    //初始化
    for (int k = 1; k <= i; k++) {
        for (int m = 1; m <= j; m++) {
            if (word1[k - 1] == word2[m - 1]) {
                dp[k][m] = dp[k - 1][m - 1];
            } else {
                int min = dp[k - 1][m - 1];
                if (dp[k - 1][m] < min)
                    min = dp[k - 1][m];
                if (dp[k][m - 1] < min)
                    min = dp[k][m - 1];
                dp[k][m] = min + 1;
            }
        }
    }
    return dp[i - 1][j - 1];
}

int main() {
    char word1[500], word2[500];
    FILE* fp = fopen("./data.in", "r");
    fscanf(fp, "%s", word1);
    fscanf(fp, "%s", word2);
    minDistance(word1, word2);
    return 0;
}
